package com.julius.design.suanfa.dynamic;

import java.util.HashMap;
import java.util.Map;

/**
 * @author julius
 * @date 2021-10-28 上午 10:04
 * <p>
 *      斐波那契数列
 *      https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
 * </p>
 */
public class FibClass {

    public static Map<Integer,Long> cache = new HashMap<>();

    static final int MOD = 1000000007;


    /**
     * 优化过的递归算法: 自顶向下
     * @param n
     * @return
     */
    public static int fib(int n) {
        long recur = recur(n);
        return (int) recur;
    }

    public static long recur(int n){
        /*
            只使用递归会出现超时现象，性能很慢，需要优化
                优化点：
                    1. 重复计算某一位置上的值
                    2.
         */
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        if(cache.containsKey(n)){
            return cache.get(n);
        }
        long re = (recur(n - 1) + recur(n - 2))%MOD;
        cache.put(n,re);
        return re;
    }


    /**
     * f(n+1) = f(n)+f(n-1)
     *
     * 滚动数组算法  自底向上
     * @return
     */
    public static int fib2(int n){
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        int ans2 = 0;
        int ans0 = 0,ans1 = 1;
        for (int i = 2;i <= n ;i++){
            ans2 = (ans0+ans1)%MOD;
            ans0 = ans1;
            ans1 = ans2;
        }
        return ans2;
    }

    public static void main(String[] args) {
        System.out.println(fib(100));
        System.out.println(fib2(100));
    }
}
